package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2022-12-19 23:18:32	 当前时间
 */
//给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 
//
// 
// 创建一个根节点，其值为 nums 中的最大值。 
// 递归地在最大值 左边 的 子数组前缀上 构建左子树。 
// 递归地在最大值 右边 的 子数组后缀上 构建右子树。 
// 
//
// 返回 nums 构建的 最大二叉树 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,1,6,0,5]
//输出：[6,3,5,null,2,0,null,null,1]
//解释：递归调用如下所示：
//- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
//    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
//        - 空数组，无子节点。
//        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
//            - 空数组，无子节点。
//            - 只有一个元素，所以子节点是一个值为 1 的节点。
//    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
//        - 只有一个元素，所以子节点是一个值为 0 的节点。
//        - 空数组，无子节点。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,1]
//输出：[3,null,2,null,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 1000 
// nums 中的所有整数 互不相同 
// 
// Related Topics 栈 树 数组 分治 二叉树 单调栈 
// 👍 604 👎 0

public class 最大二叉树{
	public static void main(String[] args) {
		Solution solution = new 最大二叉树().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/6 13:02
	 */
	public TreeNode constructMaximumBinaryTree(int[] nums) {

		if (nums.length>0){
			return  dfsByReview(nums,0,nums.length-1);
		}
		return  null;
	}

	private TreeNode dfsByReview(int[] nums, int start, int end) {
		if (start>end){
			return null;
		}
		int index = getMaxIndexByReview(nums,start,end);
		TreeNode node = new TreeNode(nums[index]);
		node.left = dfsByReview(nums,start,index-1);
		node.right = dfsByReview(nums,index+1,end);
		return node;
	}

	private int getMaxIndexByReview(int[] nums, int start, int end) {
		int max = nums[start];
		int index = start;
		if (start>end){
			return -1;
		}
		for (int i = start; i <=end; i++) {
			if (nums[i]>max){

				max = nums[i];
				index = i;
			}
		}
		return index;
	}

	// 复习end








	/**
	 * 与 构造二叉树类似：递归。
	 * 1. 找出数组最大的元素下标Index。 Node
	 * 	则 Node.left存在于 区间  nums[start,Index-1];
	 *     Node.right存在于 区间 nums[Index+1,end];
	 * 2. 若 start>end 结束。
	 */
    public TreeNode constructMaximumBinaryTreeBFS(int[] nums) {
		if (nums.length==0){
			return null;
		}
    	return 	dfs1(nums,0,nums.length-1);
    }

	private TreeNode dfs1(int[] nums, int start, int end) {
		if (start>end){
			return null;
		}
		int[] arr = getMaxIndex1(nums,start,end);
		TreeNode node = new TreeNode(arr[1]);
		node.left = dfs1(nums,start,arr[0]-1);
		node.right = dfs1(nums,arr[0]+1,end);
		return node;
	}

	private int[] getMaxIndex1(int[] nums, int start, int end) {
		int k = nums[start],index = start;
		for (int i = start;i<=end;i++){
			if (nums[i]>k){
				k = nums[i];
				index = i;
			}
		}
//		return index;
		int[] arr = new int[2];
		arr[0] = index; arr[1] = k;
		return arr;
	}
	private TreeNode dfs(int[] nums, int start, int end) {
    	if (start>end){
    		return null;
		}
		int index = getMaxIndex(nums,start,end);
		TreeNode node = new TreeNode(nums[index]);
		node.left = dfs(nums,start,index-1);
		node.right = dfs(nums,index+1,end);
		return node;
	}

	private int getMaxIndex(int[] nums, int start, int end) {
		int k = nums[start],index = start;
		for (int i = start;i<=end;i++){
			if (nums[i]>k){
				k = nums[i];
				index = i;
			}
		}
		return index;
//		int[] arr = new int[2];
//		arr[0] = index; arr[1] = k;
//		return arr;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
